/*
	Copyright (c) 2009-2011, Stefan Webb.

	This file is part of SimpleML. Please read the file "license.txt", 
	which contains the conditions under which this software is distributed.
*/

/*!
	\file parser.cpp
	\author Stefan Webb
	\brief Definition of Parser class members.
*/

#include "stdafx.h"

/* Parse contents of specified text file. */
Parser::Parser(wchar_t* filename)
{
	// Initialize variables
	initialize();

	// Open and parse file
	open(filename);
}

/* Parse string as if it was the contents of a text file. */
Parser::Parser(utf16* text, unsigned int length)
{
	// Parse text string as if from file 'filename'
	open(text, length);
}

/* Default constructor. */
Parser::Parser() {}

/* Initialize variables */
void Parser::initialize()
{
	string_ = 0;
	length_ = 0;
	filename_ = 0;
}

/* Default destructor. */
Parser::~Parser()
{
	close();
}

/* Save as specifed filename. */
bool Parser::save(wchar_t* filename)
{
	// Make sure well-formed
	if (!isReady())
		return false;

	// Get file
	wchar_t* fileString = output();

	// Open output file
	File file(filename, WRITE);

	// Make sure file opened correctly
	if (!file.isReady())
		return false;

	// This will be correct on both little and big endianness platforms
	unsigned short byteOrderMark = 0xfeff;

	// Write BOM to file
	if (!file.save(sizeof(unsigned short), (unsigned char*) &byteOrderMark))
		return false;

	// Write to file
	if (!file.save(wcslen(fileString) * 2, (unsigned char*) fileString))
		return false;

	// Free memory for string and return true
	delete [] fileString;
	return true;
}

/* Move position of cursor in specified direction. */
bool Parser::navigate(Direction direction)
{
	// Make sure well-formed
	if (!isReady())
		return false;

	// Variables
	bool wasValue = false;
	unsigned int nodeValue = 0;
	unsigned int presentNode = currentNode();

	// Switch on direction
	switch (direction) 
	{
	// Navigate to this node, i.e., do nothing
	case HERE:
		{
			return true;
		}
		break;

	// Navigate to the next node in a SAX parsing sense
	case NEXT:
		{
			// Go to the child
			if (hasChild(presentNode) || hasAttribute(presentNode)) {
				cursor.push(nodes[presentNode].child);
				return true;
			}

			// If no child then go to the sibling
			else if (hasNextSibling(presentNode)) {
				cursor.pop();
				cursor.push(nodes[presentNode].sibling);
				return true;
			}

			// If neither child nor sibling then to sibling of parent
			else {
				// Find next sibling of parents
				cursor.pop();
				while (cursor.size()) {
					presentNode = cursor.pop();
					if (hasNextSibling(presentNode)) {
						cursor.push(nodes[presentNode].sibling);
						return true;
					}
				}

				// If we get to here then there are no more nodes
				cursor.push(presentNode);
				return false;
			}
		}
		break;

	// Navigate to the previous node in a SAX parsing sense
	case PREVIOUS:
		{
			// If start node then we're done
			if (presentNode == startNode_)
				return false;

			// Go back one level
			cursor.pop();

			// If current node has a parent
			if (cursor.size()) {
				// If first child of parent is the present node then we're done
				if (nodes[currentNode()].child == presentNode)
					return true;

				// Else, go to first child
				cursor.push(nodes[currentNode()].child);
			}

			// Else if no parent then set search node to start
			else
				cursor.push(startNode_);

			// We need to find the sibling that links to the present node
			while (nodes[currentNode()].sibling != presentNode)
				cursor[cursor.size() - 1] = nodes[currentNode()].sibling;

			// Go to the deepest node from here
			while (hasChild() || hasAttribute()) {
				// Go to the child or attribute
				cursor.push(nodes[currentNode()].child);

				// Go to the last sibling of this node
				while (hasNextSibling())
					cursor[cursor.size() - 1] = nodes[currentNode()].sibling;
			}

			// Return true
			return true;
		}
		break;

	// Navigate to the child of the current node, if it has one
	case CHILD:
		{
			// Check that current node has child
			if (!hasChild(presentNode))
				return false;

			// Otherwise find first non-attribute child
			presentNode = nodes[presentNode].child;
			while (type(presentNode) == ATTR_IDENT)
				presentNode = nodes[presentNode].sibling;

			// Update cursor
			cursor.push(presentNode);
			return true;
		}
		break;

	// Navigate to the parent of the current node, if it has one
	case PARENT:
		{
			// Check that the current node has a parent
			if (!(cursor.size() - 1))
				return false;

			// Otherwise navigate to parent
			cursor.pop();
			return true;			
		}
		break;

	// Navigate to the next sibling of the current node, if it has one
	case SIBLING:
		{
			// If this is a value then pop cursor and set flag.
			if (type(presentNode) == ATTR_VALUE || type(presentNode) == INSTRUCTIONS) {
				nodeValue = cursor.pop();
				presentNode = currentNode();
				wasValue = true;
			}			

			// Find next sibling which isn't an attribute
			do {
				// If no more nodes then return false
				if (!hasNextSibling(presentNode)) {
					if (wasValue)
						cursor.push(nodeValue);
					return false;
				}

				// Navigate to next sibling
				presentNode = nodes[presentNode].sibling;

			} while (type(presentNode) == ATTR_IDENT);

			// Otherwise navigate to the sibling
			cursor.pop();
			cursor.push(presentNode);
			return true;
		}
		break;

	// Navigate to attribute, if has one
	case ATTRIBUTE:
		{
			// If this is a value then pop cursor and set flag.
			if (type(presentNode) == ATTR_VALUE) {
				nodeValue = cursor.pop();
				presentNode = currentNode();
				wasValue = true;
			}

			// If this is an attribute
			if (type(presentNode) == ATTR_IDENT) {
				// If this node doesn't have any siblings then return false
				if (!hasNextSibling(presentNode)) {
					// If it was a value then we want to restore cursor
					if (wasValue)
						cursor.push(nodeValue);
					return false;
				}

				// If the next sibling isn't an attribute then return false
				if (type(nodes[presentNode].sibling) != ATTR_IDENT) {
					// If it was a value then we want to restore cursor
					if (wasValue)
						cursor.push(nodeValue);
					return false;
				}

				// Otherwise navigate to next attribute
				cursor.pop();
				cursor.push(nodes[presentNode].sibling);
				return true;
			}

			// If this node doesn't have an attribute then return false
			if (!hasAttribute(presentNode))
				return false;

			// Otherwise go to child
			cursor.push(nodes[presentNode].child);
			return true;
		}
		break;

	// Navigate to top of this level (or to first attribute if on attributes)
	case TOP:
		{
			// If we are on the first level, then top will be start node
			if (cursor.size() == 1) {
				cursor.pop();
				cursor.push(startNode_);
				return true;
			}

			// If value or instructions then go up a level
			if (type(presentNode) == ATTR_VALUE || type(presentNode) == INSTRUCTIONS)
				cursor.pop();

			// If an attribute go to first child of parent (i.e. first attribute)
			if (type() == ATTR_IDENT) {
				cursor.pop();
				cursor.push(nodes[currentNode()].child);
			}

			// Otherwise go to first non-attribute child
			else {
				cursor.pop();
				navigate(CHILD);
			}

			return true;
		}
		break;

	// Navigate to the start of the document
	case START:
		{
			// Empty the cursor and push on it the starting node
			cursor.empty();
			cursor.push(startNode_);
		}
		break;

	// Navigate to value of attribute
	case VALUE:
		{
			// This node must be an attribute identifier
			if (type(presentNode) != ATTR_IDENT)
				return false;

			// This node must have a child
			if (!hasChild(presentNode))
				return false;

			// Otherwise, navigate to child
			cursor.push(nodes[presentNode].child);
			return true;
		}
		break;
	}

	return true;
}

/* Print file to output window. */
bool Parser::print()
{
	// Return if not ready
	if (!isReady())
		return false;

	// Get file
	wchar_t* fileString = output();

	// Print file string
	wcout << fileString << endl;

	// Free memory for string
	delete [] fileString;
	return true;
}

/* Get current node of cursor. */
unsigned int Parser::currentNode()
{
	// This function is just shorthand for the following
	return cursor[cursor.size() - 1];
}

// *** In future do a parentNode() function, i.e.,

/* Get current node of cursor.
/*unsigned int Parser::parentNode()
{
	// This function is just shorthand for the following
	return cursor[cursor.size() - 2];
}*/

// *** etc., use these functions to make code more readable.
// *** They will of course be inlined by the compiler.

/* Get current node of cursor. */
/*unsigned int Parser::nextSibling()
{
	// This function is just shorthand for the following
	return cursor[cursor.size() - 1];
}*/

/* Node type of current node. */
NodeType Parser::type()
{
	// Make sure well-formed
	if (!isReady())
		return ENDOFFILE;

	return type(currentNode());
}

/* Get type of specified node */
NodeType Parser::type(unsigned int node)
{
	return (NodeType) (descriptors[node] & NODETYPEBITS);
}

/* Gets pointer to the contents of the current node. */
utf16* Parser::value()
{
	// Make sure well-formed
	if (!isReady())
		return 0;

	utf16* offsetNode = nodes[currentNode()].offset;

	// If it was not an original node then we need to trim whitespace
	if (!isOriginalNode(currentNode())) {
		while (isWhitespace(*offsetNode))
			incrementPointer(offsetNode);
	}

	// If there is no namespace then just return the offset
	if (!hasNamespace())
		return offsetNode;

	// Otherwise, we will need to separate namespace from identifier
	while (*offsetNode++ != (utf16) L':');
	return offsetNode; // needs ++?
}

/* Extract current node into string. */
wchar_t* Parser::string()
{
	// Make sure well-formed
	if (!isReady())
		return 0;

	// Allocate memory for string
	wchar_t* nodeString = new wchar_t[length() + 1];

	// Skip namespace if it has one
	utf16* offsetIdentifier = nodes[currentNode()].offset;
	if (hasNamespace())
		while (*offsetIdentifier++ != (utf16) L':');

	// Fill out string and return
	memcpy(nodeString, offsetIdentifier, length() * sizeof(wchar_t));
	nodeString[length()] = 0;
	return nodeString;
}

/* Convert value to floating point number. */
double Parser::number()
{
	// Make sure well-formed
	if (!isReady())
		return 0;

	// Otherwise convert to double
	else
		return _wtof((wchar_t*)value());
}

/* Compares specified string to current string. */
bool Parser::isEqual(wchar_t* string)
{
	// Make sure well-formed
	if (!isReady())
		return false;

	// Otherwise compare strings
	else
		return !(bool)wcsncmp(string, (wchar_t*)value(), length());
}

/* Output file to string in XML-like syntax. */
wchar_t* Parser::output()
{
	// Pointer to string of output and length of output string
	wchar_t* stringOutput = 0;

	// The length and offset occupy same variable
	union {
		unsigned int lengthOutput;
		unsigned int offsetOutput;
	};

	// Do two passes over document. First to calculate memory, second to fill string.
	for (unsigned int j = 0; j < 2; j++) {
		// Navigate to start
		navigate(START);

		// On the second pass, allocate memory for string.
		if (j == 1)
			stringOutput = new wchar_t[lengthOutput];
		offsetOutput = 0;

		// Navigate document
		bool stillGoing = true;
		while (stillGoing == true) {
			// Get node string
			//wchar_t* nodeString = string();

			// Print this node
			switch (type()) {

			// Print character data
			case CHARDATA:
				{
					// Print character data on second pass
					if (j == 1) {
						// Put in tabs
						for (unsigned int i = 0; i < depth() - 1; i++)
							stringOutput[offsetOutput++] = L'\t';

						// Put in character data
						memcpy(&stringOutput[offsetOutput], value(), length() * sizeof(wchar_t));
						offsetOutput += length();
						
						// New line after character data
						stringOutput[offsetOutput++] = (wchar_t) 0x000d;
						stringOutput[offsetOutput++] = (wchar_t) 0x000a;
					}

					// Update length on first pass
					else
						lengthOutput += depth() + length() + 1;
				}
				break;

			// Print tag
			case TAG:
				{
					// Print tag namespace and identifier on second pass 
					if (j == 1) {
						// Put in tabs
						for (unsigned int i = 0; i < depth() - 1; i++)
							stringOutput[offsetOutput++] = L'\t';

						// Put in '<'
						stringOutput[offsetOutput++] = (wchar_t) '<';

						// Put in namespace if has one
						if (hasNamespace()) {
							// Copy namespace identifier
							memcpy(&stringOutput[offsetOutput], valueNamespace(), lengthNamespace() * sizeof(wchar_t));
							offsetOutput += lengthNamespace();

							// Put in ':'
							stringOutput[offsetOutput++] = (wchar_t) ':';
						}

						// Put in tag identifier
						memcpy(&stringOutput[offsetOutput], value(), length() * sizeof(wchar_t));
						offsetOutput += length();
					}

					// Update length on first pass
					else {
						lengthOutput += depth() + length(); 
						if (hasNamespace())
							lengthOutput += lengthNamespace() + 1;
					}

					// Deal with attributes
					if (hasAttribute()) {
						// Loop through attributes
						while (navigate(ATTRIBUTE)) {
							// Print attribute identifier on second pass
							if (j == 1) {
								// Put in space
								stringOutput[offsetOutput++] = (wchar_t) ' ';

								// Put in namespace if has one
								if (hasNamespace()) {
									// Copy namespace identifier
									memcpy(&stringOutput[offsetOutput], valueNamespace(), lengthNamespace() * sizeof(wchar_t));
									offsetOutput += lengthNamespace();

									// Put in ':'
									stringOutput[offsetOutput++] = (wchar_t) ':';
								}

								// Put in attribute identifier
								memcpy(&stringOutput[offsetOutput], value(), length() * sizeof(wchar_t));
								offsetOutput += length();

								// Put in " = "
								stringOutput[offsetOutput++] = (wchar_t) ' ';
								stringOutput[offsetOutput++] = (wchar_t) '=';
								stringOutput[offsetOutput++] = (wchar_t) ' ';
							}

							// Update length on first pass
							else {
								lengthOutput += length() + 4;
								if (hasNamespace())
									lengthOutput += lengthNamespace() + 1;
							}
						
							// Print Value
							if (hasValue()) {
								// Navigate to value
								navigate(VALUE);

								// On second pass print attribute value
								if (j == 1) {
									// Fill in opening quote
									if (hasSingleQuotes())
										stringOutput[offsetOutput++] = (wchar_t) '\"';
									else
										stringOutput[offsetOutput++] = (wchar_t) '\'';

									// Fill in attribute value
									memcpy(&stringOutput[offsetOutput], value(), length() * sizeof(wchar_t));
									offsetOutput += length();

									// Fill in ending quote
									if (hasSingleQuotes())
										stringOutput[offsetOutput++] = (wchar_t) '\"';
									else
										stringOutput[offsetOutput++] = (wchar_t) '\'';
								}

								// On first pass update length
								else
									lengthOutput += length() + 2;
								
								// Navigate back a level
								navigate(PARENT);
							}

							// If no value then print empty string
							else {
								// On second pass write empty string
								if (j == 1) {
									stringOutput[offsetOutput++] = (wchar_t) '\"';
									stringOutput[offsetOutput++] = (wchar_t) '\"';
								}

								// On first pass update length
								else
									lengthOutput += 2;
							}
						}

						// If this tag has non attribute children then we need to write '>' and continue
						if (navigate(SIBLING)) {
							// On second pass write '>' and newline
							if (j == 1) {
								stringOutput[offsetOutput++] = (wchar_t) '>';
								stringOutput[offsetOutput++] = (wchar_t) 0x000d;
								stringOutput[offsetOutput++] = (wchar_t) 0x000a;
							}

							// On first pass update length
							else
								lengthOutput+= 3;

							continue;
						}

						// Otherwise go back one level
						navigate(PARENT);
					}

					// If no attributes and no children then continue
					else if (navigate(CHILD)) {
						// On second pass write '>'
						if (j == 1) {
							stringOutput[offsetOutput++] = (wchar_t) '>';
							stringOutput[offsetOutput++] = (wchar_t) 0x000d;
							stringOutput[offsetOutput++] = (wchar_t) 0x000a;
						}

						// On first pass update length
						else
							lengthOutput+= 3;
						
						continue;
					}

					// If we got to here then there are no more children to which to navigate
					// On second pass write " />"
					if (j == 1) {
						stringOutput[offsetOutput++] = (wchar_t) ' ';
						stringOutput[offsetOutput++] = (wchar_t) '/';
						stringOutput[offsetOutput++] = (wchar_t) '>';
						stringOutput[offsetOutput++] = (wchar_t) 0x000d;
						stringOutput[offsetOutput++] = (wchar_t) 0x000a;
					}

					// On first pass update length
					else
						lengthOutput += 5;
				}
				break;

				// Print Processing instructions
			case PROCESSING:
				{
					// Print tag namespace and identifier on second pass 
					if (j == 1) {
						// Put in tabs
						for (unsigned int i = 0; i < depth() - 1; i++)
							stringOutput[offsetOutput++] = L'\t';

						// Put in "<?"
						stringOutput[offsetOutput++] = (wchar_t) '<';
						stringOutput[offsetOutput++] = (wchar_t) '?';

						// Put in namespace if has one
						if (hasNamespace()) {
							// Copy namespace identifier
							memcpy(&stringOutput[offsetOutput], valueNamespace(), lengthNamespace() * sizeof(wchar_t));
							offsetOutput += lengthNamespace();

							// Put in ':'
							stringOutput[offsetOutput++] = (wchar_t) ':';
						}

						// Put in tag identifier
						memcpy(&stringOutput[offsetOutput], value(), length() * sizeof(wchar_t));
						offsetOutput += length();
					}

					// Update length on first pass
					else {
						lengthOutput += depth() + length() + 1; 
						if (hasNamespace())
							lengthOutput += lengthNamespace() + 1;
					}

					// If it is instructions then print these
					if (hasChild()) {
						navigate(CHILD);

						// On second pass put in processing instructions
						if (j == 1) {
							// Put in ' '
							stringOutput[offsetOutput++] = (wchar_t) ' ';

							// Copy namespace identifier
							memcpy(&stringOutput[offsetOutput], value(), length() * sizeof(wchar_t));
							offsetOutput += length();							
						}

						// On first pass update length
						else
							lengthOutput += length() + 1;
						
						navigate(PARENT);
					}

					// Finish construction
					// On second pass write " ?>"
					if (j == 1) {
						stringOutput[offsetOutput++] = (wchar_t) ' ';
						stringOutput[offsetOutput++] = (wchar_t) '?';
						stringOutput[offsetOutput++] = (wchar_t) '>';
						stringOutput[offsetOutput++] = (wchar_t) 0x000d;
						stringOutput[offsetOutput++] = (wchar_t) 0x000a;
					}

					// On first pass update length
					else
						lengthOutput += 5;
				}
				break;

				// Print comment
			case COMMENT:
				{
					// On second pass put in comment
					if (j == 1) {
						// Put in tabs
						for (unsigned int i = 0; i < depth() - 1; i++)
							stringOutput[offsetOutput++] = L'\t';

						// Put in comment starter "<!--"
						stringOutput[offsetOutput++] = (wchar_t) '<';
						stringOutput[offsetOutput++] = (wchar_t) '!';
						stringOutput[offsetOutput++] = (wchar_t) '-';
						stringOutput[offsetOutput++] = (wchar_t) '-';

						// Put in comment character data
						memcpy(&stringOutput[offsetOutput], value(), length() * sizeof(wchar_t));
						offsetOutput += length();

						// Put in comment terminator and newline
						stringOutput[offsetOutput++] = (wchar_t) '-';
						stringOutput[offsetOutput++] = (wchar_t) '-';
						stringOutput[offsetOutput++] = (wchar_t) '>';
						stringOutput[offsetOutput++] = (wchar_t) 0x000d;
						stringOutput[offsetOutput++] = (wchar_t) 0x000a;
					}

					// On first pass update length
					else
						lengthOutput += depth() + length() + 8;					
				}
				break;
			}

			// Get the next node that has a sibling beneath
			while(!hasNextSibling()) {
				// If there are no more parents then we are finished
				if (!navigate(PARENT)) {
					stillGoing = false;
					break;
				}

				// Print parent
				if (type() == TAG) {
					// On second pass print closing tag
					if (j == 1) {
						// Put in tabs
						for (unsigned int i = 0; i < depth() - 1; i++)
							stringOutput[offsetOutput++] = L'\t';

						// Put in closing tag initializer
						stringOutput[offsetOutput++] = (wchar_t) '<';
						stringOutput[offsetOutput++] = (wchar_t) '/';

						// Put in namespace if has one
						if (hasNamespace()) {
							// Copy namespace identifier
							memcpy(&stringOutput[offsetOutput], valueNamespace(), lengthNamespace() * sizeof(wchar_t));
							offsetOutput += lengthNamespace();

							// Put in ':'
							stringOutput[offsetOutput++] = (wchar_t) ':';
						}

						// Put in tag identifier
						memcpy(&stringOutput[offsetOutput], value(), length() * sizeof(wchar_t));
						offsetOutput += length();

						// Put in tag terminator and newline
						stringOutput[offsetOutput++] = (wchar_t) '>';
						stringOutput[offsetOutput++] = (wchar_t) 0x000d;
						stringOutput[offsetOutput++] = (wchar_t) 0x000a;
					}
					
					// On first pass update length
					else {
						lengthOutput += depth() + length() + 4;
						if (hasNamespace())
							lengthOutput += lengthNamespace() + 1;
					}
				}
			}

			// Navigate to sibling
			navigate(SIBLING);
		}
	}

	// Return zero-terminated string

	stringOutput[offsetOutput - 2] = 0;
	return stringOutput;
}

/* Length of contents of current node, used in conjunction with value(). */
unsigned int Parser::length()
{
	// Make sure well-formed
	if (!isReady())
		return 0;

	// If there is no namespace then just return the length
	if (!hasNamespace())
		return nodes[currentNode()].length;

	// Otherwise, we will need to separate namespace from identifier
	unsigned int lengthIdentifier = nodes[currentNode()].length;
	utf16* offsetIdentifier = nodes[currentNode()].offset;
	while (*offsetIdentifier++ != (utf16) L':')
		lengthIdentifier--;
	return --lengthIdentifier;
}

/* Gets depth of the current node. */
unsigned int Parser::depth()
{
	// Make sure well-formed
	if (!isReady())
		return 0;

	return cursor.size();
}

/* Determine if current node has any children. */
bool Parser::hasChild()
{
	// Make sure well-formed
	if (!isReady())
		return false;

	return hasChild(currentNode());
}

/* Determine if current node has a parent. */
bool Parser::hasParent()
{
	// Make sure well-formed
	if (!isReady())
		return false;

	return hasParent(currentNode());
}

/* Determine if current node has any siblings. */
bool Parser::hasSibling()
{
	// Make sure well-formed
	if (!isReady())
		return false;

	return hasSibling(currentNode());
}

/* Determine if current node has sibling beneath. */
bool Parser::hasNextSibling()
{
	// Make sure well-formed
	if (!isReady())
		return false;

	return hasNextSibling(currentNode());
}


/* Determine if current node has any attributes (if tag). */
bool Parser::hasAttribute()
{
	// Make sure well-formed
	if (!isReady())
		return false;

	return hasAttribute(currentNode());
}

/* Determine if current node has a namespace. */
bool Parser::hasNamespace()
{
	// Make sure well-formed
	if (!isReady())
		return false;

	return hasNamespace(currentNode());
}

/* Determine if an attribute value is contained in single or double quotes. */
bool Parser::hasSingleQuotes()
{
	// Make sure well-formed
	if (!isReady())
		return false;

	return hasSingleQuotes(currentNode());
}

// *** In future change hasParent to isFirstChild. Makes it easier to understand.

/* Determine if current node has a parent. */
bool Parser::hasParent(unsigned int node)
{
	return descriptors[node] & HASPARENT ? true : false;
}

/* Determine if specified attribute value node uses single quotes. */
bool Parser::hasSingleQuotes(unsigned int node)
{
	return (descriptors[node] & HASSINGLEQUOTES ? true : false) && type(node) == ATTR_VALUE;
}

/* Determine if specified node has sibling. */
bool Parser::hasSibling(unsigned int node)
{
	return descriptors[node] & HASSIBLING ? true : false;
}

/* Determine if specified node has a sibling beneath it. */
bool Parser::hasNextSibling(unsigned int node) 
{
	// Sibling must not have a parent or be start node.
	if (hasParent(nodes[node].sibling) || nodes[node].sibling == startNode_)
		return false;

	// Otherwise, sibling beneath.
	return true;
}

/* Determine if specified node has child. */
bool Parser::hasChild(unsigned int node)
{
	return descriptors[node] & HASCHILD ? true : false;
}

/* Determine if specified node has namespace. */
bool Parser::hasNamespace(unsigned int node)
{
	return descriptors[node] & HASNAMESPACE ? true : false;
}

/* Determine if specified node has attribute. */
bool Parser::hasAttribute(unsigned int node)
{
	return (descriptors[node] & HASATTRIBUTE ? true : false) && type(node) == TAG;
}

/* Determine if specified attribute identifier node has value. */
bool Parser::hasValue(unsigned int node)
{
	return ((descriptors[node] & HASCHILD) ? true : false) && type(node) == ATTR_IDENT;
}

/* Determine if current node has an attribute value. */
bool Parser::hasValue()
{
	// Make sure well-formed
	if (!isReady())
		return false;

	return hasValue(currentNode());
}

/* Parse a text string with specified length */
bool Parser::open(utf16* text, unsigned int length)
{
	// Close any previously opened file
	if (isReady())
		close();

	// Set string and length
	string_ = text;
	length_ = length;

	// Parse text
	return parse();
}

/* Parse a file from specified filename. */
bool Parser::open(wchar_t* filename)
{
	// Close any previously opened file
	if (isReady())
		close();

	// Open new text
	text_.open(filename);

	// Copy filename string
	filename_ = new wchar_t[wcslen(filename) + 1];
	wcscpy(filename_, filename);

	// Make sure that it opened correctly
	if (!text_.isReady())
		return false;

	// Parse text
	return open(text_.string(), text_.size());
}

/* Parse text */
bool Parser::parse()
{
	// Start off with 16kb of nodes, 1kb of descriptors, and maximum 256 levels
	nodes.create(1024);
	descriptors.create(1024);
	cursor.create(256);
	siblings.create(256);
	freeNodes.create(128);

	// We begin in the character data parsing state
	state_ = CHARDATA;

	// Set parsing pointers and flags
	position_ = string_;
	thisLine_ = position_;
	thisNode_ = 0;
	final_ = string_ + length_; // Check this line for bug
	countLines_ = 1;
	countColumns_ = 1;
	isFirstChild_ = false;
	firstChildNode_ = 0;
	
	maximumDepth_ = 0;
	startNode_ = 0;
	hasNamespace_ = false;
	
	// Main loop for parsing. 
	// *** In the future need to make this thread-safe. ***
	// *** I.e. make ERROR state, and don't do setState(true) until end of this method ***
	while (state_ != ENDOFFILE && state_ != PARSER_ERROR)
	{
		// Switch on parsing state
		switch (state_)
		{
			// Tag parsing state
		case TAG:
			{
				parseTag();
			}
			break;

			// Character data parsing state
		case CHARDATA:
			{
				parseCharacterData();
			}
			break;

			// Processing instruction parsing state
		case PROCESSING:
			{
				parseInstructions();
			}
			break;

			// Comment parsing state
		case COMMENT:
			{
				parseComment();
			}
			break;
		}
	}

	// Get out if there was an error or file was empty
	if (state_ == PARSER_ERROR || !nodes.size()) {
		close();
		return false;
	}
	
	// Check that there are no undischarged states
	if (cursor.size()) {
		parseError(L"End-of-file and not all tags have been closed");
		close();
		return false;
	}

	// Resize cursor to right size
	cursor.create(maximumDepth_);
	cursor.push(startNode_);

	// Link last node on first level to first node
	nodes[siblings[0]].sibling = startNode_;
	descriptors[siblings[0]] |= HASSIBLING;
	siblings.destroy();

	// Set the state to true
	setState(true);
	state_ = PARSER_SUCCESS;
	return true;
}

/* Parse processing instructions. */
void Parser::parseInstructions()
{
	// Parse instruction identifier and return if error
	thisNode_ = position_;
	if (!parseIdentifier())
		return;

	// Check not end of file
	if (state_ == ENDOFFILE) {
		parseError(L"Unexpected end-of-file while parsing processing instructions");
		return;
	}

	// Otherwise save the identifier and push cursor
	// This will stop the character data being linked to as a sibling
	endNode_ = position_;
	saveNode(PROCESSING);
	
	// Start off search for character data
	if (!parseWhitespace())
		return;
	thisNode_ = position_;

	// Find the ending "?>"
	if (!parseUntil((utf16*)L"?>"))
		return;

	// If end of file then return with error
	if (state_ == ENDOFFILE) {
		parseError(L"Unexpected end-of-file while parsing processing instructions");
		return;
	}

	if (!isEmpty_) {
		// Update maximum depth
		cursor.push(nodes.size() - 1);
		if (cursor.size() > maximumDepth_)
			maximumDepth_ = cursor.size() + 1;

		// Save the processing instruction character data node
		isFirstChild_ = true;
		endNode_ = trimWhitespace(thisNode_,position_);
		saveNode(INSTRUCTIONS);
		siblings.pop();
		cursor.pop();
	}

	// Update position and state
	position_ += 2;
	state_ = CHARDATA;
}

/* Continue parsing until string is reached. Sets isEmpty flag. */
bool Parser::parseUntil(utf16* string)
{
	// Decode first character
	unsigned int length = lengthString(string);
	utf32 character = decodeCharacter(string);
	
	// Parse until string is reached
	bool isReallyEmpty = true;
	while (true) {
		// Parse until first character of string
		if (!parseUntil(character))
			return false;

		// isEmpty is reset every time parseUntil called.
		isReallyEmpty &= isEmpty_;

		// Check that we have more characters
		if (state_ == ENDOFFILE) {
			isEmpty_ = isReallyEmpty;
			return true;
		}

		// Check that we have enough characters
		if (position_ + length >= final_) {
			position_ = final_;
			isEmpty_ = isReallyEmpty;
			return true;
		}

		// Check for string
		if (compareCharacters(string, position_, length)) {
			isEmpty_ = isReallyEmpty;
			return true;
		}

		// Increment character
		incrementPosition();
	}
}

/* Search for string at current position. */
bool Parser::parseString(utf16* string)
{
	return parseString(string, lengthString(string));
}

/* Search for string at current position with given length. */
bool Parser::parseString(utf16* string, unsigned int length)
{
	// Check that we have enough characters to search for string
	if (position_ + length >= final_)
		return false;

	// Compare for string
	return compareCharacters(string, position_, length);
}

/* Parse comment. */
void Parser::parseComment()
{
	// Check that comment starts with "--"
	if (!parseString((utf16*)L"--")) {
		parseError(L"Comment must start with '<!--'");
		return;
	}

	// Skip '--'
	position_ += 2;
	countColumns_ += 2;

	// Skip whitespace
	if (!parseWhitespace())
		return;

	// Node will begin from here
	thisNode_ = position_;
	
	// Parse until next '-->' and return if error
	if (!parseUntil((utf16*) L"-->"))
		return;

	// Check not end of file
	if (state_ == ENDOFFILE) {
		parseError(L"Unexpected end-of-file while parsing comment");
		return;
	}

	// Save node if not empty
	if (!isEmpty_) {
		endNode_ = trimWhitespace(thisNode_, position_);
		saveNode(COMMENT);
	}

	// Update position and reset state
	position_ += 3;
	state_ = CHARDATA;
}

/* Parse attribute. */
bool Parser::parseAttribute()
{
	// Extract attribute identifier and save node
	thisNode_ = position_;
	if (!parseIdentifier())
		return false;
	endNode_ = position_;
	saveNode(ATTR_IDENT);
	
	// Skip whitespace and '=' sign
	if (!parseWhitespace())
		return false;
	if (position_ == final_) {
		parseError(L"Unexpected end-of-file while parsing tag");
		return false;
	}
	if (*position_++ != (utf16)L'=') {
		parseError(L"'=' must proceed attribute identifier");
		return false;
	}
	countColumns_++;
	if (!parseWhitespace())
		return false;
	if (position_ == final_) {
		parseError(L"Unexpected end-of-file while parsing tag");
		return false;
	}

	// Check for quote beginning attribute value
	if (*position_ != (utf16) L'\'' && *position_ != (utf16) L'\"') {
		parseError(L"Attribute value must begin with single or double quote");
		return false;
	}
	utf32 startQuote = (utf32) *position_;
	position_++;
	countColumns_++;

	// Extract attribute value
	if (!parseWhitespace())
		return false;
	thisNode_ = position_;
	if (!parseUntil(startQuote))
		return false;
	if (position_ == final_) {
		parseError(L"Unexpected end-of-file while parsing attribute");
		return false;
	}
	endNode_ = position_;
	position_++;
	countColumns_++;
	if (position_ == final_) {
		parseError(L"Unexpected end-of-file while parsing attribute");
		return false;
	}
	if (!isWhitespace((utf32)*position_) && *position_ != (utf16) L'/' && *position_ != (utf16) L'>') {
		parseError(L"Invalid character following attribute value");
		return false;
	}

	if (!isEmpty_) {
		cursor.push(nodes.size() - 1);

		// Update maximum depth
		if (cursor.size() > maximumDepth_)
			maximumDepth_ = cursor.size() + 1;

		// Save attribute Value
		endNode_ = trimWhitespace(thisNode_, endNode_);
		isFirstChild_ = true;
		if (startQuote == (utf32) L'\'')
			hasSmallQuotes_ = false;
		else
			hasSmallQuotes_ = true;
		saveNode(ATTR_VALUE);
		siblings.pop();
		cursor.pop();
	}

	return true;
}

/* Close parser object by freeing memory. */
void Parser::close()
{
	// Close text if open
	if (text_.isReady())
		text_.close();

	// Delete filename if created
	if (filename_)
		delete [] filename_;

	// Free memory for nodes
	deleteNodes();

	// Delete buckets
	nodes.destroy();
	descriptors.destroy();
	freeNodes.destroy();
	cursor.destroy();

	// Initialize variables
	initialize();

	// Set state to not ready
	setState(false);
}

/* Parse tag. */
void Parser::parseTag()
{
	// Clear flags
	bool isEndTag = false;
	bool isSelfClosing = false;
	
	// Check to see if end tag
	if (*position_ == '/') {
		// Update position, column, and end tag flag
		position_++;
		isEndTag = true;
		countColumns_++;

		// We must have more characters
		if (position_ == final_) {
			parseError(L"Unexpected end-of-file while parsing tag");
			return;
		}
	}

	// Tag will start from current position
	thisNode_ = position_;

	// Extract tag name
	if (!parseIdentifier())
		return;

	// Make sure we have more characters
	if (position_ == final_) {
		parseError(L"Unexpected end-of-file while parsing tag");
		return;
	}

	// Save final position of node
	endNode_ = position_;

	// Trim whitespace from after label
	if (!parseWhitespace())
		return;

	// If no more characters then throw error
	if (position_ == final_) {
		parseError(L"Unexpected end of file while parsing tag");
		return;
	}

	// Handle case when this is an end tag
	if (isEndTag) {
		// There must be '>' at current position
		if (*position_ != (utf16) L'>') {
			parseError(L"End tag must be terminated with '>'");
			return;
		}

		// Check that start and end tags have same length
		unsigned int startTag = cursor.pop();
		if (nodes[startTag].length != (unsigned int)(endNode_ - thisNode_)) {
			parseError(L"Start and end tags do not match");
			return;
		}

		// Check that start and end tags are identical
		else if (memcmp(nodes[startTag].offset, thisNode_, nodes[startTag].length * 2)) {
			parseError(L"Start and end tags do not match");
			return;
		}

		// Link first child and last sibling (even if identical)
		if (siblings.size()  == cursor.size() + 2) {
			unsigned int nodeSibling = siblings.pop();
			unsigned int firstChildNode = nodes[startTag].child;
			nodes[nodeSibling].sibling = firstChildNode;
			if (nodeSibling != firstChildNode)
				descriptors[nodeSibling] |= HASSIBLING;
		}

		// Update position and return
		position_++;
		state_ = CHARDATA;
		isFirstChild_ = false;
		return;
	}
	
	// Save tag node
	saveNode(TAG);
	cursor.push(nodes.size() - 1);

	// Update maximum depth
	if (cursor.size() > maximumDepth_)
		maximumDepth_ = cursor.size() + 1;

	// Set isFirstChild
	isFirstChild_ = true;

	// Extract attribute
	while (true) {
		// Skip whitespace
		if (!parseWhitespace())
			return;

		// If no more characters then throw error
		if (position_ == final_) {
			parseError(L"Unexpected end of file while parsing tag");
			return;
		}

		// Check for terminal characters
		if (*position_ == (utf16) L'/' || *position_ == (utf16) L'>')
			break;

		// If we got to here, then there must be attributes
		// TODO: We don't need to set attribute every time.
		// TODO: Is writing to memory slower than reading memory?
		descriptors[currentNode()] |= HASATTRIBUTE;

		// Parse attribute
		if (!parseAttribute())
			return;
		
	}

	// See if self closing tag
	if (*position_ == (utf16) L'/') {
		// If no more characters then throw error
		if (++position_ == final_) {
			parseError(L"Unexpected end of file while parsing tag");
			return;
		}

		// Pop off stack and reset first child
		if (hasAttribute(currentNode()))
			siblings.pop();
		cursor.pop();
		isFirstChild_ = false;
	}

	// Check that next character is '>'
	if (*position_++ != (utf16) L'>') {
		parseError(L"Start tag must end with '>' or '/>'");
		return;
	}

	// Update state
	state_ = CHARDATA;
}

/* Extract identifier. Identifiers are terminated by whitespace. */
bool Parser::parseIdentifier()
{
	// Check that first character of tag name is valid
	if (!isValidCharacter(position_, final_)) {
		parseError(L"Invalid character");
		return false;
	}

	// Check that letter begins identifier name
	if (subclassifyCharacter(decodeCharacter(position_)) != LETTER) {
		parseError(L"Identifier must begin with letter");
		return false;
	}
	incrementPosition();
	hasNamespace_ = false;
	isEmpty_ = false;

	// Extract tag name
	while (true) {
		// If end of file then return true
		if (position_ == final_)
			return true;

		// Check that character is valid
		else if (!isValidCharacter(position_, final_)) {
			parseError(L"Invalid character");
			return false;
		}

		// Get subcategory of character, and update position and column
		utf32 character = decodeCharacter(position_);
		GeneralCategory category = subclassifyCharacter(character);
		incrementPosition();

		// Deal with namespace
		if (character == (utf32) L':') {
			// We can only have one namespace
			if (hasNamespace_) {
				parseError(L"Identifier can only contain one ':'");
				return false;
			}

			// If end of file then return error
			if (position_ == final_) {
				parseError(L"Unexpected end-of-file while searching for identifier after namespace");
				return false;
			}

			// Check that character is valid
			else if (!isValidCharacter(position_, final_)) {
				parseError(L"Invalid character");
				return false;
			} 

			// The next character must be valid
			if (subclassifyCharacter(decodeCharacter(position_)) != LETTER) {
				parseError(L"Identifier must begin with letter");
				return false;
			}
			incrementPosition();

			// Set namespace flag
			hasNamespace_ = true;
		}

		// Identifier can contain letters and numbers.
		else if (category != LETTER && category != NUMBER) {
			// We don't want to skip this character
			decrementPosition();
			return true;
		}

		// *** I think these lines get skipped because the above else if will be invoked ***
		// If it's whitespace then this is end of identifier
		//if (isWhiteSpace(character))
		//	return true;
	}
}

/* Skip white space, while checking errors and end-of-file */
bool Parser::parseWhitespace()
{
	// Loop over string
	while (true) {
		// Check whether we have reached end of file
		if (position_ == final_) {
			return true;
		}

		// Check that surrogate pair is valid
		else if (!isValidCharacter(position_, final_)) {
			parseError(L"Invalid character");
			return false;
		}

		// Check whether we have a new line
		else if (isNewLine(position_, final_)) {
			// If so then update current line position and number
			thisLine_ = position_;
			countLines_++;
			countColumns_ = 1;
		}

		// Get out if not whitespace
		else if (!isWhitespace(*position_))
			return true;
		
		// Otherwise, change position accordingly
		else
			incrementPosition();
	}
}

/* Trim white space from end of string. */
utf16* Parser::trimWhitespace(utf16* start, utf16* end)
{
	// Loop backwards through string
	while (true) {
		// Make sure we have characters
		if (start == end)
			return start;

		// Change position accordingly
		decrementPointer(end);

		// If non-whitespace then return
		if (!isWhitespace(*end)) {
			incrementPointer(end);
			return end;
		}
	}
}

/* Increment current string position. */
void Parser::incrementPosition()
{
	// Increment position pointer
	incrementPointer(position_);

	// Increment column
	countColumns_++;
}

/* Decrement current string position. */
void Parser::decrementPosition()
{
	// Decrement position pointer
	decrementPointer(position_);

	// Decrement column
	countColumns_--;
}

void Parser::parseCharacterData()
{
	// Skip white space
	if (!parseWhitespace())
		return;

	// Set empty flag and node position
	thisNode_ = position_;

	// Parse until end-of-file or '<'
	if (!parseUntil((utf32)L'<'))
		return;

	// If there was non-whitespace then we will save this node
	if (!isEmpty_) {
		endNode_ = trimWhitespace(thisNode_, position_);
		saveNode(CHARDATA);
	}

	// If we have reached end-of-file then return
	if (state_ == ENDOFFILE)
		return;

	// We must have at least one more character
	incrementPosition();
	if (position_ == final_) {
		parseError(L"Unexpected end-of-file after tag signal '<'");
		return;
	}

	// If next character is '?' then set processing state
	if (*position_ == (utf16) L'?') {
		countColumns_++;
		position_++;
		state_ = PROCESSING;
	}

	// If next character is '!' then set comment state
	else if (*position_ == (utf16) L'!') {
		countColumns_++;
		position_++;
		state_ = COMMENT;
	}
					
	// Otherwise set tag state
	else
		state_ = TAG;
}

/* Continue parsing until character is reached. Sets isEmpty flag. */
bool Parser::parseUntil(utf32 character)
{
	// We will set isEmpty to false if non-whitespace encountered
	isEmpty_ = true;

	// Loop through string
	while (true) {
		// Check whether we have reached end of file
		if (position_ == final_) {
			// Set state and break
			state_ = ENDOFFILE;
			return true;
		}

		// Check that surrogate pair is valid
		if (!isValidCharacter(position_, final_)) {
			parseError(L"Invalid character");
			return false;
		}

		// Check whether we have a new line
		else if (isNewLine(position_, final_)) {
			// If so then update current line position and number
			thisLine_ = position_;
			countLines_++;
			countColumns_ = 1;
		}
		
		// Handle remaining cases
		else {
			// Test for our termination character
			utf32 thisCharacter = decodeCharacter(position_);
			if (character == thisCharacter)
				return true;
			incrementPosition();

			// Set flag if we have non-whitespace
			if (isEmpty_) {
				if (!isWhitespace(thisCharacter))
					isEmpty_ = false;
			}
		}
	}
}

/* Give parser error. */
void Parser::parseError(wchar_t* string)
{
	// If we're still doing the original file parsing
	if (!isReady()) {
		// Give error here
		(error << string << " in file '" << filename_  << "' on line " << countLines_ 
			<< " column " << countColumns_ << ".").warning();
		state_ = PARSER_ERROR;
	}

	// Otherwise we must be doing a modification or addition
	else {
		// Give error here
		(error << string).warning();
		//setState(false);
	}
}

/* Save node and descriptor. */
void Parser::saveNode(NodeType type)
{
	// Start off descriptor for this node
	unsigned char thisDescriptor = (unsigned char) type;

	// If namespace is present then set descriptor flag
	if (hasNamespace_) {
		thisDescriptor |= HASNAMESPACE;
		hasNamespace_ = false;
	}

	// If this is the first child then save parent position
	if (isFirstChild_) {
		// Link parent node to this node and update descriptors
		nodes[currentNode()].child = nodes.size();
		thisDescriptor |= HASPARENT;

		// Reset isFirstChild flag
		isFirstChild_ = false;
	}

	// Set has child flag if necessary
	// TODO: Is this a bug? Should it not be 
	// TODO: "descriptors[cursor[cursor.size() - 1]] |= HASCHILD;"???
	if (type != ATTR_IDENT && cursor.size())
		descriptors[currentNode()] |= HASCHILD;

	// Set quote flag if necessary
	if (type == ATTR_VALUE && hasSmallQuotes_)
		thisDescriptor |= HASSINGLEQUOTES;

	// If there was a sibling on this level then link it
	if (siblings.size() == (cursor.size() + 1)) {
		// Link sibling node to this node and update descriptor
		unsigned int nodeSibling = siblings.pop();
		nodes[nodeSibling].sibling = nodes.size();
		descriptors[nodeSibling] |= HASSIBLING;
	}

	// Add this sibling to stack
	siblings.push(nodes.size());

	// Save node and descriptor
	Node tempNode = {thisNode_, (unsigned int) (endNode_ - thisNode_), 0, 0};
	nodes.add(tempNode);
	descriptors.add(thisDescriptor);
}

/* Gets pointer to the namespace of the current node (if it has one). */
utf16* Parser::valueNamespace()
{
	// Make sure well-formed
	if (!isReady())
		return 0;

	// If there is no namespace then just return zero
	if (!hasNamespace())
		return 0;

	// Otherwise, we return namespace offset
	return nodes[currentNode()].offset;
}

/* Extract current node namespace into string. */
wchar_t* Parser::stringNamespace()
{
	// Make sure well-formed
	if (!isReady())
		return 0;

	// If there is no namespace then just return zero
	if (!hasNamespace())
		return 0;

	// Allocate memory for string
	wchar_t* nodeString = new wchar_t[lengthNamespace() + 1];

	// Fill out string and return
	memcpy(nodeString, nodes[currentNode()].offset, lengthNamespace() * sizeof(wchar_t));
	nodeString[lengthNamespace()] = 0;
	return nodeString;
}

/* Get length of namespace. */
unsigned int Parser::lengthNamespace()
{
	// Make sure well-formed
	if (!isReady())
		return 0;

	// If there is no namespace then just return zero
	if (!hasNamespace())
		return 0;

	// Otherwise, we will need to separate namespace from identifier
	unsigned int lengthIdentifier = 0;
	utf16* offsetIdentifier = nodes[currentNode()].offset;
	while (*offsetIdentifier++ != (utf16) L':')
		lengthIdentifier++;
	return lengthIdentifier; // needs --?
}

/* Insert node into document. */
bool Parser::insert(Position position, NodeType nodeType, utf16* offset, unsigned int length)
{
	Node tempNode = {0, 0, 0, 0};
	unsigned int freeNode, childNode;

	// If document is empty we will need to make this the start node
	if (!isReady()) {
		// Can only insert certain types of nodes
		if (nodeType != TAG && nodeType != CHARDATA && nodeType != PROCESSING && nodeType != COMMENT) {
			parseError(L"Invalid node-type to begin document");
			return false;
		}

		// Create buckets
		nodes.create(1024);
		descriptors.create(1024);
		cursor.create(256);
		freeNodes.create(128);

		// Insert the node
		nodes.add(tempNode);
		descriptors.push(nodeType);
		cursor.push(0);
		state_ = ENDOFFILE;
		if (!modify(offset, length)) {
			close();
			state_ = PARSER_ERROR;
			return false;
		}
		setState(true);
		startNode_ = 0;
	}

	// Otherwise insert at the given position
	else {
		// Cannot insert at instructions or attribute value
		if (type(currentNode()) == INSTRUCTIONS || type(currentNode()) == ATTR_VALUE) {
			parseError(L"Cannot insert at processing instructions or attribute values");
			return false;
		}

		// Insert inside
		if (position == INSIDE) {
			// Cannot insert inside character data or comments
			if (type(currentNode()) == CHARDATA || type(currentNode()) == COMMENT) {
				parseError(L"Cannot insert inside character data or comments");
				return false;
			}

			// Insert inside tag
			else if (type(currentNode()) == TAG) {
				// Check that nodeType is valid
				if (nodeType == INSTRUCTIONS || nodeType == ATTR_VALUE) {
					parseError(L"Cannot insert an attribute value or processing instructions inside a tag.");
					return false;
				}
				
				// If we're inserting an attribute indentifier then...
				else if (nodeType == ATTR_IDENT) {
					// Try to create node
					freeNode = createNode(nodeType, offset, length);
					if (!freeNode)
						return false;

					// If there are already attributes
					if (hasAttribute(currentNode())) {
						// If there is only one child then set HASSIBLING
						if (!hasSibling(nodes[currentNode()].child))
							descriptors[nodes[currentNode()].child] |= HASSIBLING;

						// Insert new node after first attribute. Saves having to navigate to end
						nodes[freeNode].sibling = nodes[nodes[currentNode()].child].sibling;
						nodes[nodes[currentNode()].child].sibling = freeNode;
						descriptors[freeNode] |= HASSIBLING;
					}

					// If there are no attributes
					else {
						// If this node has children
						if (hasChild(currentNode())) {
							// If there is only one child then set HASSIBLING
							if (!hasSibling(nodes[currentNode()].child))
								descriptors[nodes[currentNode()].child] |= HASSIBLING;

							// Set child to new node, link last to new node, etc.
							nodes[freeNode].sibling = nodes[currentNode()].child;
							nodes[finalSibling(nodes[currentNode()].child)].sibling = freeNode;
							descriptors[nodes[currentNode()].child] &= ~(HASPARENT);
							descriptors[freeNode] |= HASSIBLING;
						}

						// If we're here then no children or attributes
						else
							nodes[freeNode].sibling = freeNode;

						// Set the descriptor for the parent of the attribute
						descriptors[freeNode] |= HASPARENT;
						nodes[currentNode()].child = freeNode;
						descriptors[currentNode()] |= HASATTRIBUTE;
					}					
				}

				// If no children then it is simpler
				else {
					// Try to create node
					freeNode = createNode(nodeType, offset, length);
					if (!freeNode)
						return false;

					// If there are children insert after first child
					if (hasChild(currentNode())) {
						// If there is only one child then set HASSIBLING
						if (!hasSibling(nodes[currentNode()].child))
							descriptors[nodes[currentNode()].child] |= HASSIBLING;

						// Do linking
						childNode = firstChild(currentNode());
						nodes[freeNode].sibling = nodes[childNode].sibling;
						nodes[childNode].sibling = freeNode;
					}

					else {
						descriptors[currentNode()] |= HASCHILD;

						// If it has attributes but no children then insert at end
						if (hasAttribute(currentNode())) {
							// If there is only one child then set HASSIBLING
							if (!hasSibling(nodes[currentNode()].child))
								descriptors[nodes[currentNode()].child] |= HASSIBLING;

							// Do linking
							childNode = finalSibling(nodes[currentNode()].child);
							nodes[freeNode].sibling = nodes[childNode].sibling;
							nodes[childNode].sibling = freeNode;
						}

						// If we're here then it's the first node we're inserting at
						else {
							descriptors[freeNode] |= HASPARENT;
							nodes[freeNode].sibling = freeNode;
							nodes[currentNode()].child = freeNode;
							descriptors[currentNode()] |= HASCHILD;
						}
					}
				}
			}

			// Insert inside processing instructions
			else if (type(currentNode()) == PROCESSING) {
				// Check that this insert is valid
				if (hasChild(currentNode()) || nodeType != INSTRUCTIONS) {
					parseError(L"Can only insert instructions inside an empty processing instructions identifier.");
					return false;
				}

				// Try to create node
				freeNode = createNode(nodeType, offset, length);
				if (!freeNode)
					return false;

				// Modify descriptor and current node
				descriptors[freeNode] |= HASPARENT;
				descriptors[currentNode()] |= HASCHILD;
				nodes[currentNode()].child = freeNode;
			}			

			// Insert inside 
			else if (type(currentNode()) == ATTR_IDENT) {
				// Check that this insert is valid
				if (hasChild(currentNode()) || nodeType != ATTR_VALUE) {
					parseError(L"Can only insert an attribute value inside an empty attribute identifier.");
					return false;
				}

				// Try to create node
				freeNode = createNode(nodeType, offset, length);
				if (!freeNode)
					return false;

				// Modify descriptor and current node
				descriptors[freeNode] |= HASPARENT;
				descriptors[currentNode()] |= HASCHILD;
				nodes[currentNode()].child = freeNode;
			}
		}

		// Insert after or before
		else {
			// Check that this insert is valid
			if ((type(currentNode()) == ATTR_IDENT && nodeType != ATTR_IDENT) ||
				(type(currentNode()) != ATTR_IDENT && nodeType == ATTR_IDENT)) {
				parseError(L"Can only insert an attribute value before or after another attribute value.");
				return false;
			}

			// Try to create node
			freeNode = createNode(nodeType, offset, length);
			if (!freeNode)
				return false;

			// If there is only one child then set HASSIBLING
			if (!hasSibling(currentNode()))
				descriptors[currentNode()] |= HASSIBLING;

			// Do linking if after
			if (position == AFTER) {
				nodes[freeNode].sibling = nodes[currentNode()].sibling;
				nodes[currentNode()].sibling = freeNode;
			}

			// Do linking if before
			else {
				// We may need to change the start node
				if (startNode_ == currentNode())
					startNode_ = freeNode;

				// We may need to change the child of the parent
				if (isFirstChild()) {
					nodes[finalSibling(currentNode())].sibling = freeNode;
					descriptors[currentNode()] &= ~(HASPARENT);
					descriptors[freeNode] |= HASPARENT;
					nodes[cursor[cursor.size() - 2]].child = freeNode;
				}

				// Otherwise if this node is not the first child
				else
					nodes[previousSibling(currentNode())].sibling = freeNode;

				// Link new node to current node
				nodes[freeNode].sibling = currentNode();
			}
		}
	}

	// Success!
	return true;
}

/* Return first non-attribute child of node. */
unsigned int Parser::firstChild(unsigned int node)
{
	// Check that it actually has children to avoid infinite loop
	if (!hasChild(node))
		return 0;

	// Get first non attribute child
	unsigned int firstNode = nodes[node].child;
	while (type(firstNode) == ATTR_IDENT)
		firstNode = nodes[firstNode].sibling;

	return firstNode;
}

/* Create a node with given contents and type */
unsigned int Parser::createNode(NodeType nodeType, utf16* offset, unsigned int length)
{
	unsigned int freeNode = nextFreeNode();
	cursor.push(freeNode);
	descriptors[freeNode] = nodeType;
	if (!modify(offset, length)) {
		deleteNode(freeNode);
		cursor.pop();
		return 0;
	}
	cursor.pop();
	return freeNode;
}

/* Get next free node */
unsigned int Parser::nextFreeNode()
{
	const Node tempNode = {0,0,0,0};

	// If there is already a free one then return that one
	if (freeNodes.size())
		return freeNodes.extract();

	// Otherwise, we will have to make a free node
	else {
		nodes.push(tempNode);
		descriptors.push(0);
		return nodes.size() - 1;
	}
}

/* Remove current node, freeing its and its children's memory. */
void Parser::remove()
{
	// Make sure well-formed
	if (!isReady())
		return;

	// Save the current node for later
	unsigned int wascurrentNode = currentNode();

	// Removal procedure for node's descendants
	if (nodes[currentNode()].child) {
		do {
			// Go to the deepest level from here
			while (nodes[currentNode()].child)
				cursor.push(nodes[currentNode()].child);

			// Find the next node to traverse
			do {
				// Delete the node
				deleteNode(currentNode());

				// Navigate to the sibling if there is one
				if (hasNextSibling(currentNode())) {
					cursor[cursor.size() - 1] = nodes[currentNode()].sibling;
					break;
				}

				// Otherwise go back one level
				cursor.pop();
			} while (currentNode() != wascurrentNode);
		} while (currentNode() != wascurrentNode);
	}

	// Delete current node
	deleteNode(currentNode());

	// Removal procedure for node when it is the first child
	if (isFirstChild()) {
		// Connect parent to sibling if it has one, and last to first sibling
		if (hasNextSibling(currentNode())) {
			// If its an attribute and there are no more attributes then we need to toggle flag
			if (type(currentNode()) == ATTR_IDENT && type(nodes[currentNode()].sibling) != ATTR_IDENT)
				descriptors[cursor[cursor.size() - 2]] &= (unsigned char) ~(HASATTRIBUTE);

			// Connect parent to sibling, last to first sibling, and flag of new first node
			nodes[cursor[cursor.size() - 2]].child = nodes[currentNode()].sibling;
			cursor[cursor.size() - 1] = nodes[currentNode()].sibling;		
			nodes[finalSibling(currentNode())].sibling = currentNode();
			descriptors[currentNode()] |= (unsigned char) HASPARENT;
		}

		// Otherwise just sever parent from current node
		else {
			nodes[cursor[cursor.size() - 2]].child = 0;
			if (type(currentNode()) == ATTR_IDENT)
				descriptors[cursor[cursor.size() - 2]] &= (unsigned char) ~(HASATTRIBUTE);
			else
				descriptors[cursor[cursor.size() - 2]] &= (unsigned char) ~(HASCHILD);
			cursor.pop();
		}
	}

	// Removal procedure for node when it is the start node
	else if (currentNode() == startNode_) {
		// If we have a sibling then set it to be the new start node
		if (hasNextSibling(currentNode())) {
			nodes[finalSibling(startNode_)].sibling = nodes[startNode_].sibling;
			startNode_ = nodes[startNode_].sibling;
			cursor[0] = startNode_;
		}

		// If no sibling then we need to clear the document
		else
			close();
	}

	// Removal procedure for node when it is not first child or start node
	else {
		// Link previous node to current node's sibling
		unsigned int tempSibling = previousSibling(currentNode());
		nodes[tempSibling].sibling = nodes[currentNode()].sibling;

		// If the current node has siblings then the cursor will point to the sibling
		if (hasNextSibling(currentNode()))
			cursor[cursor.size() - 1] = nodes[currentNode()].sibling;

		// Otherwise set the cursor to the previous sibling
		else {
			// If the previous node is an attribute then this must be the last child
			if (type(currentNode()) != ATTR_IDENT && type(tempSibling) == ATTR_IDENT)
				descriptors[cursor[cursor.size() - 2]] &= (unsigned char) ~(HASCHILD);

			// Set cursor to previous sibling
			cursor[cursor.size() - 1] = tempSibling;
		}
	}
}

/* Get the final sibling. */
unsigned int Parser::finalSibling(unsigned int node)
{
	unsigned int lastSibling = node;
	while (hasNextSibling(lastSibling))
		lastSibling = nodes[lastSibling].sibling;
	return lastSibling;
}

/* Get the previous sibling. */
unsigned int Parser::previousSibling(unsigned int node)
{
	unsigned int previousSibling = node;
	while (nodes[previousSibling].sibling != node)
		previousSibling = nodes[previousSibling].sibling;
	return previousSibling;
}

/* Modify current node, being able to replace its value. */
bool Parser::modify(utf16* offset, unsigned int length)
{
	// Make sure well-formed
	if (state_ == PARSER_ERROR)
		return false;

	// We have to free memory if this node is not an original node
	if (nodes[currentNode()].offset && !isOriginalNode(currentNode()))
		delete [] nodes[currentNode()].offset;

	// Set parsing positions
	position_ = offset;
	final_ = offset + length;

	// If this is an identifier, need to check for namespace
	if (type(currentNode()) == TAG || type(currentNode()) == PROCESSING ||
		type(currentNode()) == ATTR_IDENT) {
			// Parse identifier
			if (!parseIdentifier())
				return false;

			// If namespace then set flag
			if (hasNamespace_)
				descriptors[currentNode()] |= HASNAMESPACE;

			// Otherwise clear flag
			else
				descriptors[currentNode()] &= ~(HASNAMESPACE);
	}

	// If it is an attribute value then check it has correct quotes
	else if (type(currentNode()) == ATTR_VALUE) {
		// Parse attribute value string
		if (!parseValue())
			return false;
		
		// If has single then set flag
		if (hasSmallQuotes_)
			descriptors[currentNode()] |= HASSINGLEQUOTES;

		// Otherwise default to double
		else
			descriptors[currentNode()] &= ~(HASSINGLEQUOTES);
	}

	// Process character data
	else if (type(currentNode()) == CHARDATA) {
		if (!parseUntil(L'<'))
			return false;
	}

	// Process processing instructions
	else if (type(currentNode()) == INSTRUCTIONS) {
		if (!parseUntil((utf16*)L"?>"))
			return false;
	}

	// Process comment
	else {
		if (!parseUntil((utf16*)L"-->"))
			return false;
	}

	// Reset state
	state_ = PARSER_SUCCESS;

	// If this string was empty then we may as well remove the node
	if (isEmpty_) {
		remove();
		return true;
	}

	// Set new values, trimming white space from end
	nodes[currentNode()].offset = offset;
	while (isWhitespace(*offset))
		incrementPointer(offset);
	nodes[currentNode()].length = trimWhitespace(offset, position_) - offset;
	return true;
}

/* Parse attribute value in string. */
bool Parser::parseValue()
{
	// Extract attribute value
	bool hasBigQuotes = false;
	hasSmallQuotes_ = false;
	if (!parseWhitespace())
		return false;
	thisNode_ = position_;
		
	// We will set isEmpty to false if non-whitespace encountered
	isEmpty_ = true;

	// Loop through string
	while (true) {
		// Check whether we have reached end of file
		if (position_ == final_)
			break;

		// Check that surrogate pair is valid
		if (!isValidCharacter(position_, final_)) {
			parseError(L"Invalid character");
			return false;
		}

		// Check whether we have a new line
		else if (isNewLine(position_, final_)) {
			// If so then update current line position and number
			thisLine_ = position_;
			countLines_++;
			countColumns_ = 1;
		}

		// Handle remaining cases
		else {
			// Test for quotes
			utf32 thisCharacter = decodeCharacter(position_);
			if (thisCharacter == L'\'')
				hasSmallQuotes_ = true;
			else if (thisCharacter == L'"')
				hasBigQuotes = true;
			incrementPosition();

			// Set flag if we have non-whitespace
			if (isEmpty_) {
				if (!isWhitespace(thisCharacter))
					isEmpty_ = false;
			}
		}
	}
		
	// We cannot have both types of quotes
	if (hasSmallQuotes_ && hasBigQuotes) {
		parseError(L"Value string contains both types of quotes.");
		return false;
	}

	// If neither we want to default to large quotes
	if (!hasSmallQuotes_ && !hasBigQuotes)
		hasSmallQuotes_ = true;

	// Success!
	return true;
}

/* Free memory for node and add to free nodes. */
void Parser::deleteNode(unsigned int node)
{
	// We have to free memory if this node is not an original node
	if (nodes[node].offset && !isOriginalNode(node))
		delete [] nodes[node].offset;

	// If it's the last one then remove from bucket
	if (node == nodes.size() - 1)
		nodes.pop();

	// Otherwise add to free nodes list, and zero offset so we know it's deleted
	else {
		freeNodes.insert(node);
		nodes[node].offset = 0;
	}
}

/* Free memory for all nodes. */
void Parser::deleteNodes()
{
	// Loop through all nodes
	for (unsigned int i = 0; i < nodes.size(); i++) {
		// We have to free memory if this node is not an original node
		if (nodes[i].offset && !isOriginalNode(i))
			delete [] nodes[i].offset;
	}
}

/* Determine if specified node was created at time of file parsing. */
bool Parser::isOriginalNode(unsigned int node)
{
	// This will be the case if the node's data belongs to string_
	if (nodes[node].offset >= string_ && (nodes[node].offset + nodes[node].length) <= string_ + length_)
		return true;

	// Otherwise not
	else
		return false;
}

/* Determine if the current node is the first child. */
bool Parser::isFirstChild()
{
	// We need to at least be on the second level
	if (cursor.size() < 2)
		return false;

	// Check the parent's child
	if (nodes[cursor[cursor.size() - 2]].child == currentNode())
		return true;
	else
		return false;
}